import com.sun.org.apache.bcel.internal.generic.ANEWARRAY;

import java.util.*;

/**
 * @author LKQ
 * @date 2022/5/12 21:06
 * @description 幷查集
 */
public class Solution3 {
    public static void main(String[] args) {
        Solution3 solution3 = new Solution3();
        int[][] grid1 = {{1,1,1,0,0}, {0,1,1,1,1}, {0,0,0,0,0}, {1,0,0,0,0}, {1,1,0,1,1}},
                grid2 = {{1,1,1,0,0}, {0,0,1,1,1}, {0,1,0,0,0},{1,0,1,1,0},{0,1,0,1,0}};
        solution3.countSubIslands(grid1, grid2);
    }
    int m, n;
    public int countSubIslands(int[][] grid1, int[][] grid2) {
        m = grid1.length;
        n = grid1[0].length;
        UnionFind unionFind = new UnionFind(m * n);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int c = getIdx(i, j);
                if (grid2[i][j] == 1) {
                    // 构造连通分量
                    if (i > 0 && grid2[i - 1][j] == 1) {
                        unionFind.union(c, getIdx(i-1, j));
                    }
                    if (j > 0 && grid2[i][j - 1] == 1) {
                        unionFind.union(c, getIdx(i, j - 1));
                    }
                }else {
                    // 为0的点，为了区别开，我们设置为parent为-1
                    unionFind.parent[c] = -1;
                }
            }
        }
        // 统计连通分量的个数
        Set<Integer> set = new HashSet<>();
        for (int i : unionFind.parent) {
            if (i != -1) {
                // 注意这里一定要添加父节点
                set.add(unionFind.find(i));
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 如果父节点 >= 0, 说明是一个连通分量，而grid1[i][j] == 0, 说明g1没有完全覆盖
                int idx = getIdx(i, j);
                if (unionFind.parent[idx] >= 0 && grid1[i][j] == 0) {
                    set.remove(unionFind.find(getIdx(i, j)));
                }
            }
        }
        return set.size();
    }

    public int getIdx(int i, int j) {
        return i * n + j;
    }
    private class UnionFind{
        int[] parent;
        UnionFind(int n) {
            parent = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }

        public int find(int x) {
            if (x != parent[x]) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        public void union(int x, int y) {
            parent[find(x)] = find(y);
        }
    }
}
